/*
题目描述：重建二叉树
条件：前序遍历和中序遍历，没有重复的元素
方法：
由前序遍历得到根节点，然后在中序遍历找到根节点所在的位置，确定左子树和右子树分别有多少节点，然后递归地构造左右子树
 */

class BinaryTreeNode{
    int value;
    BinaryTreeNode left;
    BinaryTreeNode right;
}

public class E7 {
    public static void main(String[] args){
        int[] preorder = {1,2,4,7,3,5,6,8};
        int[] inorder = {4,7,2,1,5,3,8,6};
        BinaryTreeNode tree = Construct(preorder, inorder);
        PrePrint(tree);
    }

    private static BinaryTreeNode Construct(int[] preorder, int[] inorder){
        if(preorder == null || inorder == null || preorder.length <= 0){
            return null;
        }
        return ConstructCore(preorder, inorder, 0, preorder.length - 1, 0, inorder.length - 1);
    }
    private static BinaryTreeNode ConstructCore(int[] preorder, int[] inorder, int preLeft, int preRight, int inLeft, int inRight){
        int rootValue = preorder[preLeft];
        BinaryTreeNode root = new BinaryTreeNode();
        root.value = rootValue;
        root.left = root.right = null;

        if(preLeft == preRight){
            return root;
        }

        //在中序遍历中找到根节点的值
        int rootInorder = inLeft;
        while(rootInorder <= inRight && inorder[rootInorder] != rootValue){
            rootInorder ++;
        }
        int leftLength = rootInorder - inLeft;
        if(leftLength > 0){
            //构造左子树
            root.left = ConstructCore(preorder, inorder,preLeft + 1
                    ,preLeft + leftLength, inLeft,rootInorder - 1);
        }
        if(leftLength < preRight - preLeft){
            //构造右子树
            root.right = ConstructCore(preorder, inorder, preLeft + leftLength + 1
                    , preRight, rootInorder + 1, inRight);
        }
        return root;
    }

    private static void PrePrint(BinaryTreeNode root){
        if(root == null){
            return;
        }
        System.out.print(root.value + " ");
        if(root.left != null){
            PrePrint(root.left);
        }
        if(root.right != null){
            PrePrint(root.right);
        }
    }
}
/*
1 2 4 7 3 5 6 8
 */